#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    vector<int> travesal(TreeNode *root)
    {
        vector<int> res;
        if (root == nullptr)
        {
            return res;
        }
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode *cur = que.front();
                que.pop();
                res.push_back(cur->val);
                if (cur->left)
                {
                    que.push(cur->left);
                }
                if (cur->right)
                {
                    que.push(cur->right);
                }
            }
        }
        return res;
    }

    // TreeNode *deleteNode(TreeNode *root, int key)
    // {
    //     if (root == nullptr)
    //     {
    //         return nullptr;
    //     }
    //     if (root->left == nullptr && root->right == nullptr)
    //     {
    //         if (root->val == key)
    //         {
    //             delete root;
    //             root = nullptr;
    //             return root;
    //         }
    //         else
    //         {
    //             return root;
    //         }
    //     }
    //     TreeNode *delete_node = root;
    //     TreeNode *pre = root;
    //     while (delete_node != nullptr)
    //     {
    //         if (delete_node->val < key)
    //         {
    //             pre = delete_node;
    //             delete_node = delete_node->right;
    //         }
    //         else if (delete_node->val > key)
    //         {
    //             pre = delete_node;
    //             delete_node = delete_node->left;
    //         }
    //         else
    //         {
    //             break;
    //         }
    //     }
    //     if (delete_node == nullptr)
    //     {
    //         return root;
    //     }
    //     else
    //     {
    //         TreeNode *temp = nullptr;
    //         TreeNode *pre_temp = delete_node;
    //         if (delete_node->left)
    //         {
    //             TreeNode *left_node = delete_node->left;
    //             while (left_node->right != nullptr)
    //             {
    //                 pre_temp = left_node;
    //                 left_node = left_node->right;
    //             }
    //             temp = left_node;
    //             delete_node->val = temp->val;
    //             if (pre_temp == delete_node)
    //             {
    //                 delete_node->left = temp->left;
    //                 delete temp;
    //                 temp = nullptr;
    //             }
    //             else
    //             {
    //                 pre_temp->right = temp->left;
    //                 delete temp;
    //                 temp = nullptr;
    //             }
    //         }
    //         else if (delete_node->right)
    //         {
    //             TreeNode *right_node = delete_node->right;
    //             while (right_node->left != nullptr)
    //             {
    //                 pre_temp = right_node;
    //                 right_node = right_node->left;
    //             }
    //             temp = right_node;
    //             delete_node->val = temp->val;
    //             if (pre_temp == delete_node)
    //             {
    //                 delete_node->right = temp->right;
    //                 delete temp;
    //                 temp = nullptr;
    //             }
    //             else
    //             {
    //                 pre_temp->left = temp->right;
    //                 delete temp;
    //                 temp = nullptr;
    //             }
    //         }
    //         else
    //         {
    //             if (pre->val < key)
    //             {
    //                 pre->right = nullptr;
    //             }
    //             else if (pre->val > key)
    //             {
    //                 pre->left = nullptr;
    //             }
    //             delete delete_node;
    //             delete_node = nullptr;
    //         }
    //     }
    //     return root;
    // }

    // TreeNode *deleteNode(TreeNode *root, int key)
    // {
    //     if (root == nullptr)
    //     {
    //         return root;
    //     }
    //     if (root->val == key)
    //     {
    //         if (root->left == nullptr && root->right == nullptr)
    //         {
    //             delete root;
    //             root = nullptr;
    //             return root;
    //         }
    //         else if (root->left == nullptr)
    //         {
    //             TreeNode *temp = root;
    //             root = root->right;
    //             delete temp;
    //             temp = nullptr;
    //             return root;
    //         }
    //         else if (root->right == nullptr)
    //         {
    //             TreeNode *temp = root;
    //             root = root->left;
    //             delete temp;
    //             temp = nullptr;
    //             return root;
    //         }
    //         else
    //         {
    //             TreeNode *cur = root->right;
    //             while (cur->left != nullptr)
    //             {
    //                 cur = cur->left;
    //             }
    //             cur->left = root->left;
    //             TreeNode *temp = root;
    //             root = root->right;
    //             delete temp;
    //             temp = nullptr;
    //             return root;
    //         }
    //     }
    //     else if (root->val > key)
    //     {
    //         root->left = deleteNode(root->left, key);
    //     }
    //     else if (root->val < key)
    //     {
    //         root->right = deleteNode(root->right, key);
    //     }
    //     return root;
    // }

    // TreeNode *deleteNode(TreeNode *root, int key)
    // {
    //     if (root == nullptr)
    //     {
    //         return nullptr;
    //     }
    //     if (root->val == key)
    //     {
    //         if (root->right == nullptr)
    //         {
    //             return root->left;
    //         }
    //         TreeNode *cur = root->right;
    //         while (cur->left)
    //         {
    //             cur = cur->left;
    //         }
    //         swap(root->val, cur->val);
    //     }
    //     root->left = deleteNode(root->left, key);
    //     root->right = deleteNode(root->right, key);
    //     return root;
    // }

    TreeNode *delete_one_node(TreeNode *cur)
    {
        if (cur == nullptr)
        {
            return nullptr;
        }
        if (cur->right == nullptr)
        {
            return cur->left;
        }
        TreeNode *node = cur->right;
        while (node->left)
        {
            node = node->left;
        }
        node->left = cur->left;
        return cur->right;
    }
    TreeNode *deleteNode(TreeNode *root, int key)
    {
        if (root == nullptr)
        {
            return nullptr;
        }
        TreeNode *cur = root;
        TreeNode *pre = nullptr;
        while (cur)
        {
            if (cur->val == key)
            {
                break;
            }
            pre = cur;
            if (cur->val > key)
            {
                cur = cur->left;
            }
            else
            {
                cur = cur->right;
            }
        }
        if (pre == nullptr)
        {
            return delete_one_node(cur);
        }
        if (pre->left && pre->left->val == key)
        {
            pre->left = delete_one_node(cur);
        }
        if (pre->right && pre->right->val == key)
        {
            pre->right = delete_one_node(cur);
        }
        return root;
    }
};

int main()
{
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);
    Solution sol;
    TreeNode *res = sol.deleteNode(root, 3);
    vector<int> vec = sol.travesal(res);
    for (auto num : vec)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}